package q34_searchRange;

public class Solution_1 {
    public int[] searchRange(int[] nums, int target) {
        // 先找到数组里是否存在这个数字
        if(nums.length == 0){
            return new int[] {-1,-1};
        }
        if((target < nums[0])||(target > nums[nums.length - 1])){
            return new int[] {-1,-1};
        }
        int[] range = BinarySearch(nums,0, nums.length-1, target);

        // 然后从这个数字开始，向左右分别使用二分法找到其开始的位置和结束的位置
        if (range[0] == -1) {
            return new int[] {-1, -1};
        }

        int bin = range[0];
        int start = range[1];
        int end = range[2];
        int mid;

        while (bin >= start) {
            mid = start + ((bin-start) >> 1);
            if(nums[mid] < target){
                start = mid + 1;
            }else if(nums[mid] == target){
                bin = mid - 1;
            }
        }

        bin = range[0];


        while (bin <= end) {
            mid = bin + ((end-bin) >> 1);
            if(nums[mid] > target){
                end = mid - 1;
            }else if(nums[mid] == target){
                bin = mid + 1;
            }
        }

        return new int[]{start, end};

    }
    public static int[] BinarySearch(int[] ary, int low, int high, int target)
    {
        if (high < low) return new int[] {-1,-1,-1};
        int mid = low + ((high - low) >> 1);
        if (ary[mid] == target) return new int[] {mid,low,high};
        if (ary[mid] > target) {
            return BinarySearch(ary, low, mid-1, target);
        } else {
            return BinarySearch(ary, mid + 1, high, target);
        }
    }
}
